#pragma once

// 哈希表实现

//开放地址法  ----- 线性探测
//思想 : 冲突了找下一个为空的位置插入

#include <vector>

#if 0
namespace GJG
{
	enum State
	{
		EXIST,
		EMPTY,
		DELETE
	};

	template <class Key, class Value>
	struct hash_data
	{
		pair<Key, Value> _kv;
		State _state = EMPTY;
 	};


	template <class Key, class Value>
	class hash_table
	{
		public:

			hash_table()
				:_tables(__stl_next_prime(0))
				,_n(0)
			{}

			//sgi 素数表 , 尽量控制为素数
			static const int __stl_num_primes = 28;
			inline static const unsigned long __stl_prime_list[__stl_num_primes] =
			{
			  53,         97,         193,       389,       769,
			  1543,       3079,       6151,      12289,     24593,
			  49157,      98317,      196613,    393241,    786433,
			  1572869,    3145739,    6291469,   12582917,  25165843,
			  50331653,   100663319,  201326611, 402653189, 805306457,
			  1610612741, 3221225473, 4294967291
			};

			inline unsigned long __stl_next_prime(unsigned long n)
			{
				const unsigned long* first = __stl_prime_list;
				const unsigned long* last = __stl_prime_list + __stl_num_primes;
				const unsigned long* pos = lower_bound(first, last, n);
				return pos == last ? *(last - 1) : *pos;
			}

			bool Insert(const pair<Key,Value>& kv)
			{

				//插入不允许键值冗余
				//先查找 , 若该值存在 , 插入失败
				if (Find(kv.first))
					return false;

				//扩容 , 开放地址法这里控制负载因子为在 0.7
				if ((double)_n / _tables.size() >= 0.7)
				{
					//扩容
					//思路: 建一个新的哈希表 , 旧表数据放新表
					hash_table<Key,Value> new_tables;
					//扩容
					new_tables._tables.resize(__stl_next_prime(_tables.size()+1));
					for (auto& data : _tables) // 旧表数据插入新表
					{
						if(data._state == EXIST)
							new_tables.Insert(data._kv);
					}
					_tables.swap(new_tables._tables); // _tables 变为新的表 , new_tables 出了作用域销毁
				}

#if 0			//线性探测
				//先映射 , 映射完都是整数
				//用除留余数法 -- key % N , 因为底层是 vector ,可用 size() 
				size_t hash0 = kv.first % _tables.size();
				size_t hashi = hash0;
				size_t i = 1;
				//线性探测
				while (_tables[hashi]._state == EXIST)
				{
					// 探测
					hashi = (hash0 + i) % _tables.size();
					++i; // 不断向后探测
				
				}
#endif

				//二次探测
				size_t hash0 = kv.first % _tables.size();
				size_t hashi = hash0;
				size_t i = 1;
				int flag = 1;
				while (_tables[hashi]._state == EXIST)
				{
					hashi = (hash0 + i * i * flag) % _tables.size();
					
					if (hashi < 0)
						hashi += _tables.size();

					if (flag == 1) // 还要再向左探测
					{
						flag = -1; 
					}
					else
					{
						//下一次探测
						++i;
						flag = 1;
					}
				}
			
				//insert
				_tables[hashi]._kv = kv;
				_tables[hashi]._state = EXIST;
				++_n;

				return true;
			}

			//查找按key
			hash_data<Key, Value>* Find(const Key& key)
			{
				//映射
				size_t hash0 = key % _tables.size();
				size_t hashi = hash0;
				size_t i = 1;
				while (_tables[hashi]._state != EMPTY)
				{
					if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)
					{
						return &_tables[hashi];
					}

					//探测
					hashi = (hash0 + i) % _tables.size();
					++i;
				}

				// == empty
				return nullptr;
			}
			
			bool Erase(const Key& key)
			{
				hash_data<Key, Value>* ret = Find(key);
				if (ret)
				{
					//伪删除
					ret->_state = DELETE;
					cout << ret->_kv.first << "->_state :" << ret->_state << endl;
					return true;
				}

				return false;
			}

			void print()
			{
				for (int i = 0; i < _n+1; ++i)
				{
					cout << _tables[i]._kv.first << " " << _tables[i]._kv.second << endl;
				}
				cout << endl;
			}

		private:
			vector<hash_data<Key, Value>> _tables;
			size_t _n = 0; // 有效数据个数
	};
}
#endif


//默认仿函数
template <class T>
struct HashFunc
{
	const size_t operator()(const T& key)
	{
		return (size_t)key;
	}
};


//因为 string 用的多 , 所以这里进行特化 , 那么我们就不用显示传参了 , 库中也是这么做
template <>
struct HashFunc<string>  // 这里对string 进行特化
{
	//string 转整数方法一 : 
#if 0
	//这个方法会面临 ASSIC 值加起来相等的情况 , 冲突也是有的
	size_t operator()(const string& st)
	{
		size_t hash = 0;
		//把所有 ASSIC加起来当 key
		for (auto& ch : st)
		{
			hash += ch;
		}
		return hash;
	}
#endif

	//方法二 
	//BKDR --- 字符串哈希 , 冲突几乎为0 
	size_t operator()(const string& st)
	{
		size_t hash = 0;
		//把所有 ASSIC加起来当 key
		for (auto& ch : st)
		{
			hash += ch;
			hash *= 131; // BKDR
		}
		return hash;
	}
};



//因为除留余数法要尽量保证素数, 这里采用 - >
// sgi 的素数表 
static const int __stl_num_primes = 28;
inline static const unsigned long __stl_prime_list[__stl_num_primes] =
{
  53,         97,         193,       389,       769,
  1543,       3079,       6151,      12289,     24593,
  49157,      98317,      196613,    393241,    786433,
  1572869,    3145739,    6291469,   12582917,  25165843,
  50331653,   100663319,  201326611, 402653189, 805306457,
  1610612741, 3221225473, 4294967291
};

inline unsigned long __stl_next_prime(unsigned long n)
{
	const unsigned long* first = __stl_prime_list;
	const unsigned long* last = __stl_prime_list + __stl_num_primes;
	const unsigned long* pos = lower_bound(first, last, n);
	return pos == last ? *(last - 1) : *pos;
}





//开放定址实现哈希表  
// 开放定址发是用状态标记实现插入 / 删除 .. 
namespace open_address
{

	enum State
	{
		EXIST,
		EMPTY,
		DELETE
	};


	template <class K, class V>
	struct hash_table_data
	{
		pair<K, V> _kv;
		State _state = EMPTY;
	};

	template <class K, class V , class Hash = HashFunc<K>>
	class hash_table   // 每个哈希表中的数据都是 k/v型
	{
	public:

		hash_table()
			:_tables(__stl_next_prime(0))
			, _n(0)
		{}

		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first)) // 不允许键值冗余
				return false;

			//扩容 , 这里选用负载因子 >= 0.7 扩容
			if ((double)_n / _tables.size() >= 0.7)
			{
				//扩容
				hash_table<K,V,Hash> new_table;
				new_table._tables.resize(__stl_next_prime(_tables.size() + 1));
				//旧表数据给新表
				for(auto& data : _tables)
				{
					new_table.Insert(data._kv); // 旧表数据插入新表
				}

				_tables.swap(new_table._tables); // 两表数据交换 , 新表出作用域销毁
			}



			////映射位置
			//size_t hash0 = kv.first % _tables.size();
			//size_t hashi = hash0;
			//size_t i = 1;
			////探测
			//while (_tables[hashi]._state == EXIST) // 存在继续探测
			//{
			//	//线性探测
			//	hashi = (hash0 + i) % _tables.size();
			//	++i;
			//}

			Hash hash; 
			//用仿函数
			size_t hash0 = hash(kv.first) % _tables.size();
			size_t hashi = hash0;
			size_t i = 1;
			int flag = 1;
			while (_tables[hashi]._state == EXIST)
			{
				hashi = (hash0 - i * i * flag) % _tables.size();
				
				if (hashi < 0)
					hashi += _tables.size();

				//前后探测
				if (flag == 1)
					flag = -1;

				//前后探测完成 , 进行下一次探测
				if (flag == -1)
				{
					++i;
					flag = 1;
				}
			}

			//insert
			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXIST;
			++_n;

			return true;
		}

		//查找找到了返回哈希表中数据的地址 , 哈希表中存的是哈希表数据(hash_table_data)
		//查找按 Key值
		hash_table_data<K, V>* Find(const K& key)
		{
			//映射位置
			size_t hash0 = key % _tables.size();
			size_t hashi = hash0;
			size_t i = 1;

			//查找按 Key值
			while (_tables[hashi]._state != EMPTY)
			{
				if (_tables[hashi]._state == EXIST &&
					_tables[hashi]._kv.first == key)
					return &_tables[hashi];

				//不相等继续探测
				hashi = (hash0 + i) % _tables.size();
				++i;
			}

			return nullptr;
		}

		//伪删除
		bool Erase(const K& key)
		{
			hash_table_data<K, V>* ret = Find(key);
			
			if (ret)
			{
				ret->_state = DELETE;
				return true;
			}

			return false;
		}

		//测试
		void print()
		{
			for (int i = 0; i < _n + 1; ++i)
			{
				cout << _tables[i]._kv.first << " " << _tables[i]._kv.second << endl;
			}
			cout << endl;
		}

	private:
		vector<hash_table_data<K, V>> _tables;
		size_t _n; // 记录有效数据个数 , 用于负载因子计算
	};
}


namespace hash_bucket
{
	template <class K ,class V>
	struct hash_node
	{
		pair<K, V> _kv;
		hash_node<K, V>* _next;

		hash_node(const pair<K, V>& kv)
			:_kv(kv)
			, _next(nullptr)
		{}
	};

	template <class K, class V , class Hash = HashFunc<K>>
	class hash_table
	{
		typedef hash_node<K, V> node;
	public:

		hash_table()
			:_tables(__stl_next_prime(0))
			,_num(0)
		{}


		bool Insert(const pair<K,V>& kv)
		{
			Hash hash;

			//实现不允许键值冗余版本
			if (Find(kv.first)) // 存在不插入
				return false;

			// 扩容 --- 这里采用负载因子 >= 1 
			if ((double)_num / _tables.size() >= 1)
			{
				//扩容
				//采用直接旧链表移动到新链表 , 不采用新建哈希表的方式
				
				//开一个新链表
				vector<node*> new_tables(__stl_next_prime(_tables.size() + 1));
				//用 insert 方法会一直创建新的节点 , 效率低

				//遍历旧链表一次头插新链表
				for (size_t i = 0; i < _tables.size(); ++i)
				{
					node* cur = _tables[i]; // 表示旧表中 i 下标下挂的链表
					while (cur)
					{
						//旧链表数据映射到新表
						size_t hashi = hash(cur->_kv.first) % new_tables.size();
						//头插
						// cur , new_tables[hashi]
						node* next = cur->_next;
						cur->_next = new_tables[hashi];
						new_tables[hashi] = cur;

						cur = next;
					}

					//放到新的里后旧链表当前位置置空
					_tables[i] = nullptr;
				}

				//放完以后 , 新旧交换 , 新表出作用域销毁
				_tables.swap(new_tables);
			}


			//映射
			size_t hash0 = hash(kv.first) % _tables.size();
			size_t hashi = hash0;

			//挂数据 , 这里采用头插
			node* newnode = new node(kv);
			// newnode _tables[hashi]--- >表中存的是node* 即:第一个节点的地址
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode; // 成为新的头
			++_num;

			return true;
		}

		node* Find(const K& key)
		{
			Hash hash;
			//映射
			size_t hashi = hash(key) % _tables.size();
			//遍历这个位置的链表
			node* cur = _tables[hashi];  // 这个位置的头节点的地址
			while (cur)
			{
				if (cur->_kv.first == key)
					return cur;

				cur = cur->_next;
			}

			return nullptr;
		}

		bool Erase(const K& key)
		{
			size_t hashi = key % _tables.size();  //映射位置
			node* cur = _tables[hashi];   // 映射位置的头节点
			node* prev = nullptr;
			//遍历这个位置的链表
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}

					else
					{
						//erase
						prev->_next = cur->_next;
					}

					delete cur;
					cur = nullptr;
					--_num;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}

			return false;
		}

        ~HashTable()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;

					cur = next;
				}

				_tables[i] = nullptr;
			}
		}

		void print()
		{
			for (size_t i = 0; i < _num + 1; ++i)
			{
				node* cur = _tables[i];
				cout << i << ": ";
				while (cur)
				{
					cout << cur->_kv.first << ":" << cur->_kv.second << "->";
					cur = cur->_next;
				}
				cout << endl;
			}
			cout << endl;
		}

	private:
		vector<node*> _tables;
		size_t _num; // 有效数据个数
	};

}